/*
 *  author: lichuang
 *  2010-09-25
 */

#include "quick_sort.h"
#include "common/common.h"
#include "common/array.h"
#include "ch02/insert_sort.h"

static int partion(int array[], int size) {
  int value = array[size - 1];
  int right, left;

  for (right = - 1, left = 0; left < size - 1; ++left) {
    if (array[left] <= value) {
      ++right;
      exchange(&array[right], &array[left]);
    }
  }
  exchange(&array[right + 1], &array[size - 1]);
  return right + 1;
}

static void quick_sort_impl(int array[], int size) {
  if (size > 1) {
    int pos = partion(array, size);
    quick_sort_impl(array, pos);
    quick_sort_impl(array + pos + 1, size - pos - 1);
  }
}

void quick_sort(array_t *array) {
  quick_sort_impl(array->data, array->size);
}

static void insert_quick_sort_impl(int array[], int size) {
  if (size > 5) {
    int pos = partion(array, size);
    insert_quick_sort_impl(array, pos);
    insert_quick_sort_impl(array + pos + 1, size - pos - 1);
  } else {
    insert_sort_impl(array, size);
  }
}

void insert_quick_sort(array_t *array) {
  insert_quick_sort_impl(array->data, array->size);
}

static int hoare_partion(int array[], int size) {
  int value = array[0];
  int right, left;

  for (right = -1, left = size; ; ) {
    do {
      --left;
    } while (array[left] > value);
    do {
      ++right;
    } while (array[right] < value);
    if (right < left) {
      exchange(&array[right], &array[left]);
    } else {
      return left + 1;
    }
  }
}

static void hoare_quick_sort_impl(int array[], int size) {
  if (size > 1) {
    int pos = hoare_partion(array, size);
    hoare_quick_sort_impl(array, pos);
    hoare_quick_sort_impl(array + pos + 1, size - pos - 1);
  }
}

void hoare_quick_sort(array_t *array) {
  hoare_quick_sort_impl(array->data, array->size);
}
